class Solution {
public:
  int majorityElement(vector<int>& nums) {
    
    // 摩尔投票法，总体思路就是一换一
    int current = nums[0];
    int cnt = 0;

    for(int i = 0; i < nums.size(); ++i){

      if(cnt == 0){
        current = nums[i];
      }

      current == nums[i] ? ++cnt : --cnt;

    }

    return current;

  }
};